package 牛客;

import 剑指offer.ListNode;

public class p链表的回文结构 {
    public boolean chkPalindrome(ListNode A) {
        // write code here

        //1.找中间节点
        //利用快慢指针，找到中间节点
        ListNode fast=A;
        ListNode slow=A;

        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;//fast一次走两步
            slow=slow.next;
        }

        //2.反转 后半部分的链表
        ListNode cur=slow.next;

        while (cur!=null) {
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }


        //3.一个从前往后 一个从后往前遍历，能够相遇就是回文结构
        while (A!=slow) {
            if (A.val!=slow.val) {
                return false;
            }
            //A.val==slow.val的情况
            if (A.next==slow) {
                //节点个数为 偶数时，两指针不会相遇在中间节点
                return true;
            }else {
                //节点个数为 奇数时，两指针会相遇在中间节点
                A=A.next;
                slow=slow.next;
            }
        }
        return true;
    }
}
